
/*=============================================================*
 *	Written By: Joseph Conrad Stack
 *	Unity ID:   jcstack   
 *	Date:       4-29-03
 *
 *	Description:
 *	
 *=============================================================*/
import java.util.*;
import java.io.*;
import java.lang.*;



public class ExpressionTree {
    public Stack operators = new Stack();
    public Stack operands = new Stack();
    public Stack ev = new Stack();
    public BinNode tp;
    public String express= "";
    public String post = "";
    Hashtable variables = new Hashtable();

    /** Constructs a new instance of an expression tree.
     * This constructor takes a String as a parameter containing an
     * algebraic expression.  It parses this expression and and build a new
     * instance of an expression tree.
     *
     * @param expr The String object containing the algebraic expression to
     * be parsed.
     */
    public ExpressionTree( String expr )
    {

        try {
            BufferedReader B = new BufferedReader(new FileReader(expr));
            String Line="";
            if((Line = B.readLine()) != null) {
                
                StringTokenizer ST = new StringTokenizer(Line);
                while (ST.hasMoreTokens()) {
                    String temp = ST.nextToken();

                    if (temp.equals("(")) {
                        operators.push(temp);
                    } 
                    
                    else if (temp.equals(")")) {
                        while (!(operators.peek()).equals("("))
                            buildSubTree();
                        operators.pop();
                    } 
                    
                    else if (temp.equals("%") || temp.equals("+") || temp.equals("-") || temp.equals("^") || temp.equals("/") || temp.equals("*")) {
                        while ((!operators.isEmpty()) && checkPres(operators.peek()) >= checkPres(temp))
                            buildSubTree();
                        operators.push(temp);
                    } 
                    
                    else {
                        LeafNode newRoot = new LeafNode((Object)temp);
                        operands.push(newRoot);
                    }

                }                      
            }
            // end Constructor
         
        String temp = "";
        while((Line = B.readLine()) != null){
            StringTokenizer st = new StringTokenizer(Line, ":");
            while(st.hasMoreTokens())
                variables.put(st.nextToken(),st.nextToken());
        }
        }
        catch (IOException e) {
            System.out.println("something is wrong:" + e);
        }
        //end try/catch
     
     while(!(operators.isEmpty()))
         buildSubTree();
     tp = (BinNode)operands.pop();
    }


/** builds a subtree out of subtrees and/or nodes
 * This method builds a subtree and then pushes it back onto the 
 * stack.
 */
    public void buildSubTree()
    {
        BinNode rt = (BinNode)operands.pop();
        BinNode lt = (BinNode)operands.pop();
        Character rootVal = new Character(((operators.pop()).toString()).charAt(0));
        IntNode subRoot = new IntNode(rootVal,lt,rt);
        operands.push(subRoot);
    }

    /** checks the presedence of the operator. Highest="^" to lowest="+/-"
     * This method assigns a number to operators in the order of operations
     * 
     * @return The int presedence value for the operator
     */
    public int checkPres(Object check){
        int pres = 0;
        String check1 = (String)check;
        if (check1.equals("+") || check1.equals("-"))
            pres = 1;
        if (check1.equals("*") || check1.equals("/") || check1.equals("%"))
            pres = 2;
        if (check1.equals("^"))
            pres = 3;

        return pres;

    }


 /** Performs a preorder traversal of the expression tree.
 * This method will return a String containing theexpression in its
 * prefix representation.
 *
 * @return The prefix notation for the expression stored in the tree.
 */
    public String preorder()
    {
        BinNode tRoot = tp;
        String output = "";
        operands.push(tp);
        while( !(operands.isEmpty()) )
        {
            while(tRoot.left() != null)
            {
               output += tRoot.element().toString();
                operands.push(tRoot);
                tRoot = tRoot.left();
                if (tRoot.left() == null)
                   output += tRoot.element().toString();
            }
            tRoot = (BinNode)operands.pop();
    	    tRoot = tRoot.right();
            if(tRoot.left() == null)
            	output += tRoot.element().toString();
        }

        return output;
    
    }
       

        

    /** Performs a postorder traversal of the expression tree.
     * This method will return a String containing the expression in its
     * postfix representation.
     *
     * @return The postfix notation for the expression stored in the tree.
     */
    public String postorder()
    {
    BinNode postRoot = tp;
    post = "";
    String output = helperPost(postRoot);
    return output;
    
    } // end postorder
    
    
    
    /** Performs the actual postorder traversal
     * this returns a string to the postorder() method.
     * 
     * @return the postfix notation for the expression in the tree
     */
    public String helperPost(BinNode temp){
        if(temp.left() != null)
            helperPost(temp.left());
        if(temp.right() != null)
            helperPost(temp.right());
        post += temp.element();
        return post;
    }

    
    /** Preforms inorder traversal
     * This method returns the infix notation of the expression in the tree
     * using a helper method.
     * 
     * @return The infix notation of the expression
     */ 
    public String inorder(){
        BinNode inRoot = tp;
        express = "";
        String output = helper(inRoot);
        return output;
    }
    
    /** Used in conjuction with the inorder method
     * This method does the actual work of creating the infix notation in a String
     * 
     * @return The infix notation of the expression
     */ 
    public String helper(BinNode temp){
        if(!temp.isLeaf())
        express += "( ";
        
        if(temp.left() != null)
            helper(temp.left());
        if(variables.containsKey(temp.element()))
           temp.setElement(variables.get(temp.element()));
        express += temp.element()+ " ";
        if(temp.right() != null)
            helper(temp.right());
        
        if(!temp.isLeaf())
            express += ") ";
        
        return express;
    }

    /** Evaluates the expression string
     * This method can only be called after the inorder() method(to work correctly. 
     * it uses a helper method to evaluate each sub expression and pushed it back 
     * on the stack.
     * 
     * @return The int value of the executed expression
     */ 
    public int evaluate(){
        StringTokenizer eval = new StringTokenizer(express);
        while(eval.hasMoreTokens()){
            String p = eval.nextToken();
            if(p.equals(")"))
                evalHelper();
            else if(!(p.equals("("))){
                if(variables.containsKey(p))
                  p = (variables.get((Object)p)).toString();
                ev.push((Object)p);
            }
        }
    Integer yes = new Integer((ev.pop()).toString());
    return yes.intValue();
    }

    public void evalHelper(){
        int temp = 0;
        Integer rightOperand = new Integer((ev.pop()).toString());
        String op = (String)ev.pop();
        Integer leftOperand = new Integer((ev.pop()).toString());
        if(op.equals("-"))
            temp = leftOperand.intValue() - rightOperand.intValue();
        if(op.equals("+"))
            temp = leftOperand.intValue() + rightOperand.intValue();
        if(op.equals("/"))
            temp = leftOperand.intValue() / rightOperand.intValue();
        if(op.equals("*"))
            temp = leftOperand.intValue() * rightOperand.intValue();
        if(op.equals("%"))
            temp = leftOperand.intValue() % rightOperand.intValue();
        if(op.equals("^")){
            double tmp = Math.pow(leftOperand.doubleValue(),rightOperand.doubleValue());
            temp = (int)tmp;
        }
        ev.push(new Integer(temp));
    }


} // end class
